#include<iostream>
#include<windows.h>

using namespace std;

#define MAXSIZE 20

typedef int ElemType;

typedef struct LNode
{
	ElemType data;		//节点的数据域
	struct LNode* next;	//指向LNode类型的指针，用来指向下一个节点。
}LinkNode,LinkList;

//初始化
//指针引用的主要目的是允许函数内部修改传递进来的指针，并且这个修改在函数外部是可见的。
//如果不使用指针引用，在函数内部对 L 的赋值只会影响函数内部的局部指针，而不会改变函数外部传递的指针
bool initLink(LinkList*& L)	
{
	//分配内存空间
	L = new LinkNode;
	if (!L) return false;	//生成节点失败
	L->next = NULL;
	L->data = -1;
	return true;
}

//销毁
void destoryLink(LinkList* L)
{
	//定义一个临时节点p指向L
	LinkNode* p = L;
	cout << "销毁链表！" << endl;
	while (p)
	{
		L = L->next;
		delete p;	//删除当前节点
		p = L;	//p移动到下一个节点
	}
}

//在指定位置插入元素
bool insertLink(LinkList* L, int pos, ElemType e)
{
	if (!L) return false;	//为空
	int j = 1;
	LinkList *p, *q;
	p = L;
	//查找pos，让p指向该节点
	while (p && (j < pos))
	{
		p = p->next;
		++j;
	}
	if (!p || j > pos) return false;
	//生成一个新的节点
	q = new LinkNode;
	q->data = e;
	q->next = p->next;
	p->next = q;
	return true;
}

//删除指定位置的元素
bool deleteLink(LinkList* L, int pos)
{
	if (!L || !L->next) return false;
	int j = 1;
	LinkList *p, *q;
	p = L;
	while (p->next && j < pos)
	{
		p = p->next;
		++j;
	}
	if (!p->next || j > pos) return false;

	q = p->next;
	p->next = q->next;
	delete q;

	return true;
}

//头插法建立单链表
bool inserHeadList(LinkList* L, LinkNode* node)
{
	if (!L || !node) return false;

	node->next = L->next;
	L->next = node;
	return true;
}

//尾插法建立单链表
bool inserTailList(LinkList* L, LinkNode* node)
{
	if (!L || !node) return false;

	LinkNode* last;
	last = L;

	while (last->next) last = last->next;
	node->next = NULL;
	last->next = node;
	return true;
}

//打印单链表
void printList(LinkList* L)
{
	LinkNode* p = NULL;
	if (!L) cout << "链表为空！" << endl;

	p = L->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

//求链表的长度
int getLength(LinkList* L)
{
	int len = 0;
	LinkNode* p = L;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	return len - 1;
}

//查找指定元素（带头节点）
int getElem(LinkList* L, ElemType e)
{
	LinkNode* p = L->next;
	int pos = 1;
	while (p != NULL)
	{
		if (p->data == e)
		{
			return pos;
			break;
		}
		pos++;
		p = p->next;
	}
	return -1;
}

int main2()
{
	LinkList* L = NULL;
	LinkNode* s = NULL;
	if (initLink(L)) cout << "正在初始化链表..." << endl;
	else cout << "初始化失败！" << endl;
	int n;
	/*
	cout << "头插法建立单链表：" << endl;
	cout << "请输入你要插入的元素个数：";
	cin >> n;
	cout << endl << "请依次插入元素：" << endl;
	while (n > 0)
	{
		s = new LinkNode;
		cin >> s->data;
		inserHeadList(L, s);
		n--;
	}*/
	cout << "尾插法建立单链表：" << endl;
	cout << "请输入你要插入的元素个数：";
	cin >> n;
	cout << endl << "请依次插入元素：" << endl;
	while (n > 0)
	{
		s = new LinkNode;
		cin >> s->data;
		inserTailList(L, s);
		n--;
	}
	cout << "单链表如下所示：" << endl;
	printList(L);
	Sleep(1000);
	cout << "单链表的长度为：" << getLength(L) << endl;
	int pos, e;
	cout << "请输入要插入的位置和元素值：" << endl;
	cin >> pos >> e;
	if (insertLink(L, pos, e)) cout << "插入成功！" << endl;
	else cout << "插入失败！" << endl;
	Sleep(2000);
	printList(L);
	cout << endl << "请输入要删除的位置：" << endl;
	cin >> pos;
	if (deleteLink(L, pos)) cout << "删除成功！" << endl;
	else cout << "删除失败！" << endl;
	printList(L);
	cout << endl << "请输入你要查找的元素值：" << endl;
	cin >> e;
	pos = getElem(L,e);
	if (pos != -1)cout << "该元素在第" << pos << "处！" << endl;
	else cout << "没有找到！" << endl;
	Sleep(2000);
	destoryLink(L);

	return 0;
}